package leetcode

import kotlinetc.println

//https://leetcode.com/problems/word-break-ii/
/**
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]
[wordBreak]类似
 */
fun main(args: Array<String>) {

    wordBreakII("pineapplepenapple", listOf("apple", "pen", "applepen", "pine", "pineapple")).println()

//    wordBreakII("catsandog", listOf("cats", "dog", "sand", "and", "cat")).println()
}

//DP
fun wordBreakII(s: String, wordDict: List<String>): List<String> {

    var result = arrayListOf<String>()
    val dp = Array<ArrayList<Int>>(s.length + 1, { arrayListOf() })
    val wordSet = wordDict.toHashSet()
    dp[0].add(0)//just not empty for true

    for (i in 0 until s.length + 1) {

        for (j in 0 until i + 1) {
            if (dp[j].isNotEmpty() && wordSet.contains(s.substring(j, i))) {
                //found a separate position
                dp[i].add(j)
            }
        }
    }

    //根据保存的dp来分割字符串

    findBreakWorRecursive(result, s, "", dp, s.length)
    return result
}

fun findBreakWorRecursive(result: ArrayList<String>, ss: String, s: String, dp: Array<ArrayList<Int>>, len: Int) {
    //去除space
    if (len == 0) {
        result.add(s.trim())
        return
    }

    val breakList = dp[len]

    breakList.forEach {
        findBreakWorRecursive(result, ss, " " + ss.substring(it, len) + s, dp, it)
    }
}
